Bienvenue dans la leçon 3 de Concepts d'intelligence artificielle (PolyU COMP5511). Dans cette session, nous passons de la recherche de chemin mono-agent à la Recherche adversariale, où les agents évoluent dans des environnements multi-agents compétitifs. Nous introduisons également les Problèmes de satisfaction de contraintes (CSP), un paradigme où l'objectif est de trouver un état qui satisfait un ensemble spécifique de restrictions plutôt qu'un chemin.
Concepts clés
- Recherche adversariale : Se concentre sur des algorithmes comme Minimax et Élagage Alpha-Bêta pour prendre des décisions rationnelles face à un adversaire intelligent.
- Recherche arborescente Monte-Carlo (MCTS) : Explore la prise de décision probabiliste, et constitue la pierre angulaire des IA de jeu modernes comme AlphaGo.
- Satisfaction de contraintes : Modélise les problèmes à l'aide de variables, domaines et contraintes, résolus par Retour sur trace et Recherche locale.
Analyse de complexité
Dans les contextes adversariaux, la complexité de l'espace de recherche est souvent définie par le facteur de branchement du jeu
Avertissement : changement de paradigme
Contrairement à la recherche standard (par exemple A* ou BFS) où l'environnement est statique, la Recherche adversariale part du principe que l'environnement (l'adversaire) cherche activement à minimiser votre réussite. Dans les CSP, l'ordre des actions importe moins que la validité de l'affectation finale.
Pseudocode conceptuel : types d'agents
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).